#include <iostream>
#include <queue>
#include <vector>
// 判断人，狼,羊,菜所在此岸还彼岸
bool farmer(int status)
{
    return ((status&0x08) != 0);
}
bool wolf(int status)
{
    return ((status&0x04)!=0);
}
bool cabbage(int status)
{
    return ((status&0x02)!=0);
}
bool goat(int status)
{
    return ((status&0x01)!=0);
}
// 安全状态检查
bool safe(int status)
{
    if((goat(status) == cabbage(status))&&(goat(status) != farmer(status)))
        return false;
    else if(goat(status) == wolf(status) && (wolf(status)!=farmer(status)))
        return false;
    else
        return true;
}
void solve()
{
    int END = 15;
    int movers,i,location,newlocation,status=0,newstatus;
    std::vector<int> route(END+1,-1);
    std::queue<int> moveTo;
    moveTo.push(0x00);
    route[0] = 0;
    while(!moveTo.empty()&&route[15] == -1) {
        status = moveTo.front();
        moveTo.pop();
        for (movers = 1; movers <= 8; movers <<= 1) {
            int same = (status&movers);
            // 判断农夫和移动的物品是不是在同一边(同一边才能移动)
            if (farmer(status) == (bool) (status & movers)) {
                // 0x08|movers状态为移动后的状态
                newstatus = status ^ (0x08 | movers);
                // 判断状态安全与否，羊菜和羊狼不能在人不在的时候在同一边。
                if (safe(newstatus) && (route[newstatus] == -1)) {
                    route[newstatus] = status;
                    moveTo.push(newstatus);
                }
            }
        }
    }
    if(route[15]!=-1)
    {
        std::cout<<"Reverse path is:"<<std::endl;
        for(int status=15;status>=0;status=route[status])
        {
            std::cout<<"The status is: "<<status<<"\n";
            if(status == 0)
                break;
        }
    }
    else
        std::cout<<"No solution."<<"\n";

}
int main() {
    solve();
    return 0;
}